package 队列与栈;

import java.util.Stack;

//使括号有效的最少添加
//https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid/
class 有效括号的最少添加 {
    public int minAddToMakeValid1(String s) {
        Stack<Character> stack = new Stack<>();
        int ans = 0;// 记录添加的右括号
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push('(');
            } else if (s.charAt(i) == ')') {
                if (stack.isEmpty()) {
                    ans++;
                } else {
                    stack.pop();
                }
            }
        }

        return ans + stack.size();
    }

    public int minAddToMakeValid(String s) {
        int left = 0;// 记录添加的左括号
        int right = 0;// 记录添加的右括号
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                left++;
            } else if (c == ')') {
                if (left == 0) {
                    right++;
                } else {
                    left--;
                }
            }
        }

        return right + left;
    }
}
